package com.it.od.od2024;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author: liminghui
 * @date: 2024/1/23 23:32
 * @version: 1.0
 * @description: 游戏分组/王者荣耀: dfs 10个选5个
 * 输入
 * 1 2 3 4 5 6 7 8 9 10
 * 输出
 * 1
 */
public class Main6 {
    public static void main(String[] args) {
        // Set<Integer> set1 = new HashSet<>();
        // set1.add(2);
        // set1.add(1);
        // set1.add(3);
        // Set<Integer> set2 = new HashSet<>();
        // set2.add(1);
        // set2.add(2);
        // set2.add(3);
        // Set<Set<Integer>> sets = new HashSet<>();
        // sets.add(set1);
        // sets.add(set2);
        // set1.equals(set2);
        // System.out.println(sets); // set可以直接去重

        // Scanner sc = new Scanner(System.in);
        // int[] arr = new int[10];
        // for (int i = 0; i < 10; i++) {
        //     arr[i]=sc.nextInt();
        // }


        int[] arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int totalSum = Arrays.stream(arr).sum();
        boolean[] visited = new boolean[10];
        Set<Integer> candidate = new HashSet<>();
        Set<Set<Integer>> result = new HashSet<>();

        dfs(arr, candidate, visited, result);

        // 求分差最小的
        int minDiff = Integer.MAX_VALUE;
        for (Set<Integer> set : result) {
            Integer sum1 = set.stream().reduce(Integer::sum).orElse(0);
            Integer diff = Math.abs(totalSum - sum1 - sum1);
            minDiff = Math.min(minDiff, diff);
        }
        System.out.println(minDiff);

    }

    public static void dfs(int[] arr, Set<Integer> candidate, boolean[] visited, Set<Set<Integer>> result) {
        Set<Integer> newCandidate = new HashSet<>(candidate);
        if (newCandidate.size() == 5) {
            result.add(newCandidate);
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (visited[i]) {
                continue;
            }
            visited[i] = true;
            newCandidate.add(arr[i]);
            dfs(arr, newCandidate, visited, result);
            visited[i] = false;
            newCandidate.remove(arr[i]);
        }
    }
}
